package org.example.algorithm.LinkList;

import java.util.HashMap;
import java.util.Map;

/**
 * 思路，hash表，和双端链表
 */
public class LRUCache implements ILRUCache{

    class DoubleNode{

        private int key;

        private int value;

        private DoubleNode prev;

        private DoubleNode next;

        DoubleNode(int key, int value){
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    private Map<Integer, DoubleNode> map;

    private DoubleNode head;

    private DoubleNode tail;

    private int capacity;

    private int size;

    public LRUCache(int capacity){
        this.capacity = capacity;
        this.size = 0;
        this.map = new HashMap<>();
        //两个虚拟节点
        head = new DoubleNode(0 ,0);
        tail = new DoubleNode(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DoubleNode node = map.getOrDefault(key, null);
        if(node == null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    private void moveToHead(DoubleNode node){
        //因为有虚拟节点，所以不需要判断对应的头尾节点
        removeNode(node);
        addToHead(node);
    }

    private void addToHead(DoubleNode node) {
        //node的前继节点指向head
        node.prev = head;
        //node的后继节点指向
        node.next = head.next;
        //原来的第一个节点的前继节点要指向对应的node节点
        head.next.prev = node;
        //头节点的后继指向node
        head.next = node;
    }

    private void removeNode(DoubleNode node) {
        //node的前继节点，指向的next要从node调整为node的下一个
        node.prev.next = node.next;
        //node的后继节点，指向的prev要从node调整为node的上一个
        node.next.prev = node.prev;
    }

    private DoubleNode removeTail(){
        DoubleNode res = tail.prev;
        removeNode(res);
        return res;
    }

    public void put(int key, int value) {
        //看看这个在不在缓存里
        DoubleNode node = map.get(key);
        if(node != null){
            node.value = value;
            moveToHead(node);
        }else{
            //如果不存在，先创造一个节点
            DoubleNode curr = new DoubleNode(key, value);
            map.put(key, curr);
            addToHead(curr);
            size++;
            if(size > capacity){
                DoubleNode doubleNode = removeTail();
                map.remove(doubleNode.key);
                size--;
            }
        }
    }
}
